//
// Created by gushen610140 on 2024/4/16.
//

#ifndef DATASTRUCTURECOURSE_GTHREADINGTREE_H
#define DATASTRUCTURECOURSE_GTHREADINGTREE_H

#include <iostream>

enum Tag {
    Child,
    Thread
};

template<typename T>
class GThreadingNode {
public:
    T data;
    GThreadingNode<T> *left, *right;
    Tag lTag, rTag;

    explicit GThreadingNode(T data) : data(data),
                                      left(nullptr),
                                      right(nullptr),
                                      lTag(Child),
                                      rTag(Child) {}
};

template<typename T>
class [[maybe_unused]] GThreadingTree {
private:
    GThreadingNode<T> *_root;

    GThreadingNode<T> *_createPreorder() {
        T value;
        std::cin >> value;
        if (value == '#') return nullptr;
        auto *node = new GThreadingNode<T>(value);
        node->left = _createPreorder();
        node->right = _createPreorder();
        return node;
    }

    void _threadInorder(GThreadingNode<T> *node, GThreadingNode<T> *&prev) {
        if (node) {
            // 向左子树递归完之后再改变 prev 的值
            _threadInorder(node->left, prev);
            // 当前节点的前驱
            if (!node->left) {
                node->lTag = Thread;
                node->left = prev;
            }
            // 前驱节点的后继
            if (!prev->right) {
                prev->rTag = Thread;
                prev->right = node;
            }
            // 这个时候再改变 prev 的值
            prev = node;
            _threadInorder(node->right, prev);
        }
    }

    void _threadPreorder(GThreadingNode<T> *node, GThreadingNode<T> *&prev) {
        if (node) {
            if (!node->left) {
                node->lTag = Thread;
                node->left = prev;
            }
            if (prev && !prev->right) {
                prev->rTag = Thread;
                prev->right = node;
            }

            // 保存右子树，在改变上一个结点的后续中右子树可能会被改变
            auto saveRight = node->right;

            // 从第一个结点就开始改变 prev 的值
            prev = node;

            // 当线索产生后不再进入
            if (node->lTag == Child) {
                _threadPreorder(node->left, prev);
            }
            if (node->rTag == Child) {
                _threadPreorder(saveRight, prev);
            }
        }
    }

    void _threadPostorder(GThreadingNode<T> *node, GThreadingNode<T> *&prev) {
        if (node) {
            if (node->lTag == Child) {
                _threadPostorder(node->left, prev);
            }
            if (node->rTag == Child) {
                _threadPostorder(node->right, prev);
            }

            if (!node->left) {
                node->lTag = Thread;
                node->left = prev;
            }
            if (prev && !prev->right) {
                prev->rTag = Thread;
                prev->right = node;
            }

            // 左子树递归完之后再改变 prev 的值
            prev = node;
        }
    }

public:
    GThreadingTree() : _root(nullptr) {}

    [[maybe_unused]] void createPreorder() {
        _root = _createPreorder();
    }

    [[maybe_unused]] void threadInorder() {
        auto *dummy = new GThreadingNode<T>(' ');
        dummy->lTag = Child;
        dummy->rTag = Thread;
        dummy->right = dummy;
        if (!_root) {
            dummy->left = dummy;
        } else {
            dummy->left = _root;
            GThreadingNode<T> *prev = dummy;
            _threadInorder(_root, prev);
            prev->rTag = Thread;
            prev->right = dummy;
            dummy->right = prev;
        }
        _root = dummy;
    }

    [[maybe_unused]] void printInorder() {
        GThreadingNode<T> *traversal = _root->left;
        while (traversal->lTag == Child) {
            traversal = traversal->left;
        }
        while (traversal != _root) {
            std::cout << traversal->data;
            // 如果是线索，可以直接访问
            if (traversal->rTag == Thread) {
                traversal = traversal->right;
            } // 如果是孩子，需要向右子树中序遍历，所以要找到右孩子最左边
            else {
                traversal = traversal->right;
                while (traversal->lTag == Child) {
                    traversal = traversal->left;
                }
            }
        }
    }

    [[maybe_unused]] void threadPreorder() {
        auto dummy = new GThreadingNode<T>(' ');
        dummy->lTag = Child;
        dummy->rTag = Thread;
        dummy->right = dummy;
        if (!_root) {
            dummy->left = dummy;
        } else {
            dummy->left = _root;
            GThreadingNode<T> *prev = dummy;
            _threadPreorder(_root, prev);
            prev->rTag = Thread;
            prev->right = dummy;
            dummy->right = prev;
        }
        _root = dummy;
    }

    [[maybe_unused]] void printPreorder() {
        GThreadingNode<T> *traversal = _root->left;
        while (traversal != _root) {
            std::cout << traversal->data;
            if (traversal->lTag == Child) {
                traversal = traversal->left;
            } else {
                traversal = traversal->right;
            }
        }
    }

    [[maybe_unused]] void threadPostorder() {
        auto dummy = new GThreadingNode<T>(' ');
        dummy->lTag = Child;
        dummy->rTag = Thread;
        dummy->right = dummy;
        if (!_root) {
            dummy->left = dummy;
        } else {
            dummy->left = _root;
            GThreadingNode<T> *prev = dummy;
            _threadPostorder(_root, prev);

            // 根节点才是最后一个结点， 改变 prev 的值
            _root->right = prev;
            _root->rTag = Thread;
            prev = _root;

            // 修改根节点与 dummy 的关系
            prev->rTag = Thread;
            prev->right = dummy;
            dummy->right = prev;
        }
        _root = dummy;
    }

    // 后续线索二叉树需要访问当前结点的父节点，因此需要额外的参数来保存父节点
    // 这里以抽象函数模拟读取父节点操作
    virtual GThreadingNode<T> *getParent(GThreadingNode<T> *node) {}

    [[maybe_unused]] void printPostorder() {
        GThreadingNode<T> *traversal = _root->left;
        while (traversal->lTag == Child) {
            traversal = traversal->left;
        }
        while (traversal != _root) {
            std::cout << traversal->data;
            auto parent = getParent(traversal);
            if (parent->right == traversal || parent->rTag == Thread) {
                traversal = parent;
            } else {
                traversal = traversal->right;
                while (traversal->lTag == Child) {
                    traversal = traversal->left;
                }
            }
        }
    }
};

#endif //DATASTRUCTURECOURSE_GTHREADINGTREE_H
